home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / os2 / pccts.zip / MISC.C < prev    next >
C/C++ Source or Header  |  1992-12-08  |  26KB  |  924 lines
  1. /*
  2.  * misc.c
  3.  *
  4.  * Manage tokens, regular expressions.
  5.  * Print methods for debugging
  6.  * Compute follow lists onto tail ends of rules.
  7.  *
  8.  * The following functions are visible:
  9.  *
  10.  *        int        addTname(char *);        Add token name
  11.  *        int        addTexpr(char *);        Add token expression
  12.  *        int        Tnum(char *);            Get number of expr/token
  13.  *        void    Tlink(char *, char *);    Link a name with an expression
  14.  *        int        hasAction(expr);        Does expr already have action assigned?
  15.  *        void    setHasAction(expr);        Indicate that expr now has an action
  16.  *        Entry    *newEntry(char *,int);    Create new table entry with certain size
  17.  *        void    list_add(ListNode **list, char *e)
  18.  *        void    list_apply(ListNode *list, void (*f)())
  19.  *        void    lexclass(char *m);        switch to new/old lexical class
  20.  *        void    lexmode(int i);            switch to old lexical class i
  21.  *
  22.  * SOFTWARE RIGHTS
  23.  *
  24.  * We reserve no LEGAL rights to the Purdue Compiler Construction Tool
  25.  * Set (PCCTS) -- PCCTS is in the public domain.  An individual or
  26.  * company may do whatever they wish with source code distributed with
  27.  * PCCTS or the code generated by PCCTS, including the incorporation of
  28.  * PCCTS, or its output, into commerical software.
  29.  * 
  30.  * We encourage users to develop software with PCCTS.  However, we do ask
  31.  * that credit is given to us for developing PCCTS.  By "credit",
  32.  * we mean that if you incorporate our source code into one of your
  33.  * programs (commercial product, research project, or otherwise) that you
  34.  * acknowledge this fact somewhere in the documentation, research report,
  35.  * etc...  If you like PCCTS and have developed a nice tool with the
  36.  * output, please mention that you developed it using PCCTS.  In
  37.  * addition, we ask that this header remain intact in our source code.
  38.  * As long as these guidelines are kept, we expect to continue enhancing
  39.  * this system and expect to make other tools available as they are
  40.  * completed.
  41.  *
  42.  * ANTLR 1.06
  43.  * Terence Parr
  44.  * Purdue University
  45.  * 1989-1992
  46.  */
  47. #include <stdio.h>
  48. #include "set.h"
  49. #include "syn.h"
  50. #include "hash.h"
  51. #include "generic.h"
  52. #include "dlgdef.h"
  53.  
  54. static int tsize=TSChunk;        /* size of token str arrays */
  55.  
  56.                 /* T o k e n  M a n i p u l a t i o n */
  57.  
  58. /*
  59.  * add token 't' to the TokenStr/Expr array.  Make more room if necessary.
  60.  * 't' is either an expression or a token name.
  61.  *
  62.  * There is only one TokenStr array, but multiple ExprStr's.  Therefore,
  63.  * for each lex class (element of lclass) we must extend the ExprStr array.
  64.  * ExprStr's and TokenStr are always all the same size.
  65.  *
  66.  * Also, there is a Texpr hash table for each automaton.
  67.  */
  68. static void
  69. Ttrack(t)
  70. char *t;
  71. {
  72.     if ( TokenNum >= tsize )    /* terminal table overflow? */
  73.     {
  74.         char **p;
  75.         int i, more, j;
  76.  
  77.         more = TSChunk * (1 + ((TokenNum-tsize) / TSChunk));
  78.         tsize += more;
  79.         TokenStr = (char **) realloc(TokenStr, tsize*sizeof(char *));
  80.         require(TokenStr != NULL, "Ttrack: can't extend TokenStr");
  81.         for (i=0; i<NumLexClasses; i++)
  82.         {
  83.             lclass[i].exprs = (char **)
  84.                               realloc(lclass[i].exprs, tsize*sizeof(char *));
  85.             require(lclass[i].exprs != NULL, "Ttrack: can't extend ExprStr");
  86.             for (p= &lclass[i].exprs[tsize-more],j=1; j<=more; j++) *p++ = NULL;
  87.         }
  88.         for (p= &TokenStr[tsize-more],i=1; i<=more; i++) *p++ = NULL;
  89.         lexmode( CurrentLexClass ); /* reset ExprStr in case table moved */
  90.     }
  91.     if ( *t == '"' ) ExprStr[TokenNum] = t;
  92.     else TokenStr[TokenNum] = t;
  93. }
  94.  
  95. static Expr *
  96. newExpr(e)
  97. char *e;
  98. {
  99.     Expr *p = (Expr *) calloc(1, sizeof(Expr));
  100.     require(p!=NULL, "newExpr: cannot alloc Expr node");
  101.  
  102.     p->expr = e;
  103.     p->lclass = CurrentLexClass;
  104.     return p;
  105. }
  106.  
  107. /* switch to lexical class/mode m.  This amounts to creating a new
  108.  * lex mode if one does not already exist and making ExprStr point
  109.  * to the correct char string array.  We must also switch Texpr tables.
  110.  *
  111.  * BTW, we need multiple ExprStr arrays because more than one automaton
  112.  * may have the same label for a token, but with different expressions.
  113.  * We need to track an expr for each automaton.  If we disallowed this
  114.  * feature, only one ExprStr would be required.
  115.  */
  116. void
  117. lexclass(m)
  118. char *m;
  119. {
  120.     int i;
  121.     TermEntry *p;
  122.     static char EOFSTR[] = "\"@\"";
  123.  
  124.     if ( hash_get(Tname, m) != NULL )
  125.     {
  126.         warn(eMsg1("lexclass name conflicts with token/errclass label '%s'",m));
  127.     }
  128.     /* does m already exist? */
  129.     i = LexClassIndex(m);
  130.     if ( i != -1 ) {lexmode(i); return;}
  131.     /* must make new one */
  132.     NumLexClasses++;
  133.     CurrentLexClass = NumLexClasses-1;
  134.     require(NumLexClasses<=MaxLexClasses, "number of allowable lexclasses exceeded\nIncrease MaxLexClasses in generic.h and recompile all C files");
  135.     lclass[CurrentLexClass].class = m;
  136.     lclass[CurrentLexClass].exprs = (char **) calloc(tsize, sizeof(char *));
  137.     require(lclass[CurrentLexClass].exprs!=NULL,
  138.             "lexclass: cannot allocate ExprStr");
  139.     lclass[CurrentLexClass].htable = newHashTable();
  140.     ExprStr = lclass[CurrentLexClass].exprs;
  141.     Texpr = lclass[CurrentLexClass].htable;
  142.     /* define EOF for each automaton */
  143.     p = newTermEntry( EOFSTR );
  144.     p->token = EofToken;
  145.     hash_add(Texpr, EOFSTR, (Entry *)p);
  146.     list_add(&ExprOrder, (void *)newExpr(EOFSTR));
  147.     ExprStr[EofToken] = EOFSTR;
  148. }
  149.  
  150. void
  151. lexmode(i)
  152. int i;
  153. {
  154.     require(i<NumLexClasses, "lexmode: invalid mode");
  155.     ExprStr = lclass[i].exprs;
  156.     Texpr = lclass[i].htable;
  157.     CurrentLexClass = i;
  158. }
  159.  
  160. /* return index into lclass array of lexical class. return -1 if nonexistent */
  161. int
  162. LexClassIndex(class)
  163. char *class;
  164. {
  165.     int i;
  166.  
  167.     for (i=0; i<NumLexClasses; i++)
  168.     {
  169.         if ( strcmp(lclass[i].class, class) == 0 ) return i;
  170.     }
  171.     return -1;
  172. }
  173.  
  174. int
  175. hasAction(expr)
  176. char *expr;
  177. {
  178.     TermEntry *p;
  179.     require(expr!=NULL, "hasAction: invalid expr");
  180.  
  181.     p = (TermEntry *) hash_get(Texpr, expr);
  182.     require(p!=NULL, eMsg1("hasAction: expr '%s' doesn't exist",expr));
  183.     return (p->action!=NULL);
  184. }
  185.  
  186. void
  187. setHasAction(expr,action)
  188. char *expr, *action;
  189. {
  190.     TermEntry *p;
  191.     require(expr!=NULL, "setHasAction: invalid expr");
  192.  
  193.     p = (TermEntry *) hash_get(Texpr, expr);
  194.     require(p!=NULL, eMsg1("setHasAction: expr '%s' doesn't exist",expr));
  195.     p->action = action;
  196. }
  197.  
  198. /*
  199.  * Add a token name.  Return the token number associated with it.  If it already
  200.  * exists, then return the token number assigned to it.
  201.  *
  202.  * Track the order in which tokens are found so that the DLG output maintains
  203.  * that order.  It also lets us map token numbers to strings.
  204.  */
  205. int
  206. addTname(token)
  207. char *token;
  208. {
  209.     TermEntry *p;
  210.     require(token!=NULL, "addTname: invalid token name");
  211.  
  212.     if ( (p=(TermEntry *)hash_get(Tname, token)) != NULL ) return p->token;
  213.     p = newTermEntry( token );
  214.     Ttrack( p->str );
  215.     p->token = TokenNum++;
  216.     hash_add(Tname, token, (Entry *)p);
  217.     return p->token;
  218. }
  219.  
  220. /*
  221.  * Add a token expr.  Return the token number associated with it.  If it already
  222.  * exists, then return the token number assigned to it.
  223.  */
  224. int
  225. addTexpr(expr)
  226. char *expr;
  227. {
  228.     TermEntry *p;
  229.     require(expr!=NULL, "addTexpr: invalid regular expression");
  230.  
  231.     if ( (p=(TermEntry *)hash_get(Texpr, expr)) != NULL ) return p->token;
  232.     p = newTermEntry( expr );
  233.     Ttrack( p->str );
  234.     /* track the order in which they occur */
  235.     list_add(&ExprOrder, (void *)newExpr(p->str));
  236.     p->token = TokenNum++;
  237.     hash_add(Texpr, expr, (Entry *)p);
  238.     return p->token;
  239. }
  240.  
  241. /* return the token number of 'term'.  Return 0 if no 'term' exists */
  242. int
  243. Tnum(term)
  244. char *term;
  245. {
  246.     TermEntry *p;
  247.     require(term!=NULL, "Tnum: invalid terminal");
  248.     
  249.     if ( *term=='"' ) p = (TermEntry *) hash_get(Texpr, term);
  250.     else p = (TermEntry *) hash_get(Tname, term);
  251.     if ( p == NULL ) return 0;
  252.     else return p->token;
  253. }
  254.  
  255. /* associate a Name with an expr.  If both have been already assigned
  256.  * token numbers, then an error is reported.  Add the token or expr
  257.  * that has not been added if no error.  This 'represents' the #token
  258.  * ANTLR pseudo-op.  If both have not been defined, define them both
  259.  * linked to same token number.
  260.  */
  261. void
  262. Tlink(token,expr)
  263. char *token, *expr;
  264. {
  265.     TermEntry *p, *q;
  266.     require(token!=NULL && expr!=NULL, "Tlink: invalid token name and/or expr");
  267.  
  268.     p = (TermEntry *) hash_get(Tname, token);
  269.     q = (TermEntry *) hash_get(Texpr, expr);
  270.     if ( p != NULL && q != NULL )    /* both defined */
  271.     {
  272.         warn( eMsg2("token name %s and rexpr %s already defined; ignored",
  273.                     token, expr) );
  274.         return;
  275.     }
  276.     if ( p==NULL && q==NULL )        /* both not defined */
  277.     {
  278.         int t = addTname( token );
  279.         q = newTermEntry( expr );
  280.         hash_add(Texpr, expr, (Entry *)q);
  281.         q->token = t;
  282.         ExprStr[t] = q->str;
  283.         /* track the order in which they occur */
  284.         list_add(&ExprOrder, (void *)newExpr(q->str));
  285.         return;
  286.     }
  287.     if ( p != NULL )                /* one is defined, one is not */
  288.     {
  289.         q = newTermEntry( expr );
  290.         hash_add(Texpr, expr, (Entry *)q);
  291.         q->token = p->token;
  292.         ExprStr[p->token] = q->str;    /* both expr and token str defined now */
  293.         list_add(&ExprOrder, (void *)newExpr(q->str));
  294.     }
  295.     else                            /* trying to associate name with expr here*/
  296.     {
  297.         p = newTermEntry( token );
  298.         hash_add(Tname, token, (Entry *)p);
  299.         p->token = q->token;
  300.         TokenStr[p->token] = p->str;/* both expr and token str defined now */
  301.     }
  302. }
  303.  
  304. /*
  305.  * Given a string, this function allocates and returns a pointer to a
  306.  * hash table record of size 'sz' whose "str" pointer is reset to a position
  307.  * in the string table.
  308.  */
  309. Entry *
  310. newEntry(text,sz)
  311. char *text;
  312. int sz;
  313. {
  314.     Entry *p;
  315.     require(text!=NULL, "new: NULL terminal");
  316.     
  317.     if ( (p = (Entry *) calloc(1,sz)) == 0 )
  318.     {
  319.         fatal("newEntry: out of memory for terminals\n");
  320.         exit(1);
  321.     }
  322.     p->str = strdup(text);
  323.     
  324.     return(p);
  325. }
  326.  
  327. /*
  328.  * add an element to a list.
  329.  *
  330.  * Any non-empty list has a sentinel node whose 'elem' pointer is really
  331.  * a pointer to the last element.  (i.e. length(list) = #elemIn(list)+1).
  332.  * Elements are appended to the list.
  333.  */
  334. void
  335. list_add(list,e)
  336. ListNode **list;
  337. void *e;
  338. {
  339.     ListNode *p, *tail;
  340.     require(e!=NULL, "list_add: attempting to add NULL list element");
  341.  
  342.     p = newListNode;
  343.     require(p!=NULL, "list_add: cannot alloc new list node");
  344.     p->elem = e;
  345.     if ( *list == NULL )
  346.     {
  347.         ListNode *sentinel = newListNode;
  348.         require(sentinel!=NULL, "list_add: cannot alloc sentinel node");
  349.         *list=sentinel;
  350.         sentinel->next = p;
  351.         sentinel->elem = (char *)p;        /* set tail pointer */
  352.     }
  353.     else                                /* find end of list */
  354.     {
  355.         tail = (ListNode *) (*list)->elem;    /* get tail pointer */
  356.         tail->next = p;
  357.         (*list)->elem = (char *) p;        /* reset tail */
  358.     }
  359. }
  360.  
  361. void
  362. list_apply(list,f)
  363. ListNode *list;
  364. void (*f)();
  365. {
  366.     ListNode *p;
  367.     require(f!=NULL, "list_apply: NULL function to apply");
  368.  
  369.     if ( list == NULL ) return;
  370.     for (p = list->next; p!=NULL; p=p->next) (*f)( p->elem );
  371. }
  372.  
  373.             /* F O L L O W  C y c l e  S t u f f */
  374.         
  375. /* make a key based upon (rulename, computation, k value).
  376.  * Computation values are 'i'==FIRST, 'o'==FOLLOW.
  377.  */
  378. char *
  379. Fkey(rule,computation,k)
  380. char *rule;
  381. int computation;
  382. int k;
  383. {
  384.     static char key[MaxRuleName+2+1];
  385.     int i;
  386.     
  387.     if ( k > 255 ) 
  388.         fatal("k>255 is too big for this implementation of ANTLR!\n");
  389.     if ( (i=strlen(rule)) > MaxRuleName )
  390.         fatal( eMsgd("rule name > max of %d\n", MaxRuleName) );
  391.     strcpy(key,rule);
  392.     key[i] = computation;
  393.     key[i+1] = (char) ((unsigned int) k);
  394.     key[i+2] = '\0';
  395.     return key;
  396. }
  397.  
  398. /* Push a rule onto the kth FOLLOW stack */
  399. void
  400. FoPush(rule,k)
  401. char *rule;
  402. int k;
  403. {
  404.     RuleEntry *r;
  405.     require(rule!=NULL, "FoPush: tried to push NULL rule");
  406.     require(k<=LL_k,    "FoPush: tried to access non-existent stack");
  407.  
  408.     /*fprintf(stderr, "FoPush(%s)\n", rule);*/
  409.     r = (RuleEntry *) hash_get(Rname, rule);
  410.     if ( r == NULL ) {fatal( eMsg1("rule %s must be defined but isn't", rule) );}
  411.     if ( FoStack[k] == NULL )        /* Does the kth stack exist yet? */
  412.     {
  413.         /*fprintf(stderr, "allocating FoStack\n");*/
  414.         FoStack[k] = (int *) calloc(FoStackSize, sizeof(int));
  415.         require(FoStack[k]!=NULL, "FoPush: cannot allocate FOLLOW stack\n");
  416.     }
  417.     if ( FoTOS[k] == NULL )
  418.     {
  419.         FoTOS[k]=FoStack[k];
  420.         *(FoTOS[k]) = r->rulenum;
  421.     }
  422.     else
  423.     {
  424. #ifdef MEMCHK
  425.         require(valid(FoStack[k]), "FoPush: invalid FoStack");
  426. #endif
  427.         if ( FoTOS[k] >= &(FoStack[k][FoStackSize-1]) )
  428.             fatal( eMsgd("exceeded max depth of FOLLOW recursion (%d)\n",
  429.                         FoStackSize) );
  430.         require(FoTOS[k]>=FoStack[k],
  431.                 eMsg1("FoPush: FoStack stack-ptr is playing out of its sandbox",
  432.                       rule));
  433.         ++(FoTOS[k]);
  434.         *(FoTOS[k]) = r->rulenum;
  435.     }
  436.     {
  437.         /*
  438.         int *p;
  439.         fprintf(stderr, "FoStack[k=%d]:\n", k);
  440.         for (p=FoStack[k]; p<=FoTOS[k]; p++)
  441.         {
  442.             fprintf(stderr, "\t%s\n", RulePtr[*p]->rname);
  443.         }
  444.         */
  445.     }
  446. }
  447.  
  448. /* Pop one rule off of the FOLLOW stack.  TOS ptr is NULL if empty. */
  449. void
  450. FoPop(k)
  451. int k;
  452. {
  453.     require(k<=LL_k, "FoPop: tried to access non-existent stack");
  454.     /*fprintf(stderr, "FoPop\n");*/
  455.     require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
  456.             "FoPop: FoStack stack-ptr is playing out of its sandbox");
  457.     if ( FoTOS[k] == FoStack[k] ) FoTOS[k] = NULL;
  458.     else (FoTOS[k])--;
  459. }
  460.  
  461. /* Compute FOLLOW cycle.
  462.  * Mark all FOLLOW sets for rules in cycle as incomplete.
  463.  * Then, save cycle on the cycle list (Cycles) for later resolution.
  464.  * The Cycle is stored in the form:
  465.  *        (head of cycle==croot, rest of rules in cycle==cyclicDep)
  466.  *
  467.  * e.g. (Fo means "FOLLOW of", "-->" means requires or depends on)
  468.  *
  469.  *        Fo(x)-->Fo(a)-->Fo(b)-->Fo(c)-->Fo(x)
  470.  *                                           ^----Infinite recursion (cycle)
  471.  *
  472.  * the cycle would be: x -> {a,b,c} or stored as (x,{a,b,c}).  Fo(x) depends
  473.  * on the FOLLOW of a,b, and c.  The root of a cycle is always complete after
  474.  * Fo(x) finishes.  Fo(a,b,c) however are not.  It turns out that all rules
  475.  * in a FOLLOW cycle have the same FOLLOW set.
  476.  */
  477. void
  478. RegisterCycle(rule,k)
  479. char *rule;
  480. int k;
  481. {
  482.     CacheEntry *f;
  483.     Cycle *c;
  484.     int *p;
  485.     RuleEntry *r;
  486.     require(rule!=NULL, "RegisterCycle: tried to register NULL rule");
  487.     require(k<=LL_k,    "RegisterCycle: tried to access non-existent stack");
  488.  
  489.     /*fprintf(stderr, "RegisterCycle(%s)\n", rule);*/
  490.     /* Find cycle start */
  491.     r = (RuleEntry *) hash_get(Rname, rule);
  492.     require(r!=NULL,eMsg1("rule %s must be defined but isn't", rule));
  493.     require(FoTOS[k]>=FoStack[k]&&FoTOS[k]<=&(FoStack[k][FoStackSize-1]),
  494.             eMsg1("RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox",
  495.                   rule));
  496. /*    if ( FoTOS[k]<FoStack[k]||FoTOS[k]>&(FoStack[k][FoStackSize-1]) )
  497.     {
  498.         fprintf(stderr, "RegisterCycle(%s): FoStack stack-ptr is playing out of its sandbox\n",
  499.                         rule);
  500.         fprintf(stderr, "RegisterCycle: sp==0x%x out of bounds 0x%x...0x%x\n",
  501.                         FoTOS[k], FoStack[k], &(FoStack[k][FoStackSize-1]));
  502.         exit(-1);
  503.     }
  504. */
  505. #ifdef MEMCHK
  506.     require(valid(FoStack[k]), "RegisterCycle: invalid FoStack");
  507. #endif
  508.     for (p=FoTOS[k]; *p != r->rulenum && p >= FoStack[k]; --p) {;}
  509.     require(p>=FoStack[k], "RegisterCycle: FoStack is screwed up beyond belief");
  510.     if ( p == FoTOS[k] ) return;    /* don't worry about cycles to oneself */
  511.     
  512.     /* compute cyclic dependents (rules in cycle except head) */
  513.     c = newCycle;
  514.     require(c!=NULL, "RegisterCycle: couldn't alloc new cycle");
  515.     c->cyclicDep = empty;
  516.     c->croot = *p++;        /* record root of cycle */
  517.     for (; p<=FoTOS[k]; p++)
  518.     {
  519.         /* Mark all dependent rules as incomplete */
  520.         f = (CacheEntry *) hash_get(Fcache, Fkey(RulePtr[*p]->rname,'o',k));
  521.         if ( f==NULL )
  522.         {
  523.             f = newCacheEntry( Fkey(RulePtr[*p]->rname,'o',k) );
  524.             hash_add(Fcache, Fkey(RulePtr[*p]->rname,'o',k), (Entry *)f);
  525.         }
  526.         f->incomplete = TRUE;
  527.         
  528.         set_orel(*p, &(c->cyclicDep)); /* mark rule as dependent of croot */
  529.     }
  530.     list_add(&(Cycles[k]), (void *)c);
  531. }
  532.  
  533. /* make all rules in cycle complete
  534.  *
  535.  * while ( some set has changed ) do
  536.  *        for each cycle do
  537.  *            if degree of FOLLOW set for croot > old degree then
  538.  *                update all FOLLOW sets for rules in cyclic dependency
  539.  *                change = TRUE
  540.  *            endif
  541.  *        endfor
  542.  * endwhile
  543.  */
  544. void
  545. ResolveFoCycles(k)
  546. int k;
  547. {
  548.     ListNode *p, *q;
  549.     Cycle *c;
  550.     int changed = 1;
  551.     CacheEntry *f,*g;
  552.     int r,d,i;
  553.     
  554.     /*fprintf(stderr, "Resolving following cycles for %d\n", k);*/
  555.     while ( changed )
  556.     {
  557.         changed = 0;
  558.         i = 0;
  559.         for (p = Cycles[k]->next; p!=NULL; p=p->next)
  560.         {
  561.             c = (Cycle *) p->elem;
  562.             /*fprintf(stderr, "cycle %d: %s -->", i++, RulePtr[c->croot]->rname);*/
  563.             /*s_fprT(stderr, c->cyclicDep);*/
  564.             /*fprintf(stderr, "\n");*/
  565.             f = (CacheEntry *)
  566.                     hash_get(Fcache, Fkey(RulePtr[c->croot]->rname,'o',k));
  567.             require(f!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[c->croot]->rname) );
  568.             if ( (d=set_deg(f->fset)) > c->deg )
  569.             {
  570.                 /*fprintf(stderr, "Fo(%s) has changed\n", RulePtr[c->croot]->rname);*/
  571.                 changed = 1;
  572.                 c->deg = d;        /* update cycle FOLLOW set degree */
  573.                 while ( !set_nil(c->cyclicDep) )
  574.                 {
  575.                     r = set_int(c->cyclicDep);
  576.                     set_rm(r, c->cyclicDep);
  577.                     /*fprintf(stderr, "updating Fo(%s)\n", RulePtr[r]->rname);*/
  578.                     g = (CacheEntry *)
  579.                             hash_get(Fcache, Fkey(RulePtr[r]->rname,'o',k));
  580.                     require(g!=NULL, eMsg1("FOLLOW(%s) must be in cache but isn't", RulePtr[r]->rname) );
  581.                     set_orin(&(g->fset), f->fset);
  582.                     g->incomplete = FALSE;
  583.                 }
  584.             }
  585.         }
  586.         if ( i == 1 ) changed = 0;    /* if only 1 cycle, no need to repeat */
  587.     }
  588.     /* kill Cycle list */
  589.     for (q = Cycles[k]->next; q != NULL; q=p)
  590.     {
  591.         p = q->next;
  592.         set_free( ((Cycle *)q->elem)->cyclicDep );
  593.         free(q);
  594.     }
  595.     free( Cycles[k] );
  596.     Cycles[k] = NULL;
  597. }
  598.  
  599.  
  600.             /* P r i n t i n g  S y n t a x  D i a g r a m s */
  601.  
  602. static void
  603. pBlk(q,btype)
  604. Junction *q;
  605. int btype;
  606. {
  607.     int k;
  608.     Junction *alt;
  609.  
  610.     q->end->visited = TRUE;
  611.     if ( btype == aLoopBegin )
  612.     {
  613.         require(q->p2!=NULL, "pBlk: invalid ()* block");
  614.         PRINT(q->p1);
  615.         alt = (Junction *)q->p2;
  616.         PRINT(alt->p1);
  617.         if ( PrintAnnotate )
  618.         {
  619.             printf(" /* Opt ");
  620.             k = 1;
  621.             while ( !set_nil(alt->fset[k]) )
  622.             {
  623.                 s_fprT(stdout, alt->fset[k]);
  624.                 if ( k++ == LL_k ) break;
  625.                 if ( !set_nil(alt->fset[k]) ) printf(", ");
  626.             }
  627.             printf(" */\n");
  628.         }
  629.         return;
  630.     }
  631.     for (alt=q; alt != NULL; alt= (Junction *) alt->p2 )
  632.     {
  633.         if ( alt->p1 != NULL ) PRINT(alt->p1);
  634.         if ( PrintAnnotate )
  635.         {
  636.             printf( " /* [%d] ", alt->altnum);
  637.             k = 1;
  638.             while ( !set_nil(alt->fset[k]) )
  639.             {
  640.                 s_fprT(stdout, alt->fset[k]);
  641.                 if ( k++ == LL_k ) break;
  642.                 if ( !set_nil(alt->fset[k]) ) printf(", ");
  643.             }
  644.             if ( alt->p2 == NULL && btype == aOptBlk )
  645.                 printf( " (optional branch) */\n");
  646.             else printf( " */\n");
  647.         }
  648.         if ( alt->p2 != NULL && !(((Junction *)alt->p2)->p2==NULL && btype == aOptBlk) )
  649.         {
  650.             printf(" |");
  651.         }
  652.     }
  653.     q->end->visited = FALSE;
  654. }
  655.  
  656. /* How to print out a junction */
  657. void
  658. pJunc(q)
  659. Junction *q;
  660. {
  661.     int dum_k;
  662.     int doing_rule;
  663.     require(q!=NULL, "pJunc: NULL node");
  664.     require(q->ntype==nJunction, "pJunc: not junction");
  665.     
  666.     if ( q->visited == TRUE ) return;
  667.     q->visited = TRUE;
  668.     switch ( q->jtype )
  669.     {
  670.         case aSubBlk :
  671.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  672.             if ( q->end->p1 != NULL && ((Junction *)q->end->p1)->ntype==nJunction &&
  673.                  ((Junction *)q->end->p1)->jtype == EndRule ) doing_rule = 1;
  674.             else doing_rule = 0;
  675.             if ( doing_rule ) pBlk(q,q->jtype);
  676.             else { printf(" ("); pBlk(q,q->jtype); printf(" )\n"); }
  677.             if ( PrintAnnotate ) freeBlkFsets(q);
  678.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  679.             break;
  680.         case aOptBlk :
  681.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  682.             printf(" {"); pBlk(q,q->jtype); printf(" }");
  683.             if ( PrintAnnotate ) freeBlkFsets(q);
  684.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  685.             break;
  686.         case aLoopBegin :
  687.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  688.             printf(" ("); pBlk(q,q->jtype); printf(" )*");
  689.             if ( PrintAnnotate ) freeBlkFsets(q);
  690.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  691.             break;
  692.         case aLoopBlk :
  693.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  694.             pBlk(q,q->jtype);
  695.             if ( PrintAnnotate ) freeBlkFsets(q);
  696.             break;
  697.         case aPlusBlk :
  698.             if ( PrintAnnotate ) First(q, 1, q->jtype, &dum_k);
  699.             printf(" ("); pBlk(q,q->jtype); printf(" )+");
  700.             if ( PrintAnnotate ) freeBlkFsets(q);
  701.             if ( q->end->p1 != NULL ) PRINT(q->end->p1);
  702.             break;
  703.         case EndBlk :
  704.             break;
  705.         case RuleBlk :
  706.             printf( "\n%s :", q->rname);
  707.             PRINT(q->p1);
  708.             if ( q->p2 != NULL ) PRINT(q->p2);
  709.             break;
  710.         case Generic :
  711.             if ( q->p1 != NULL ) PRINT(q->p1);
  712.             q->visited = FALSE;
  713.             if ( q->p2 != NULL ) PRINT(q->p2);
  714.             break;
  715.         case EndRule :
  716.             printf( " ;\n");
  717.             break;
  718.     }
  719.     q->visited = FALSE;
  720. }
  721.  
  722. /* How to print out a rule reference node */
  723. void
  724. pRuleRef(p)
  725. RuleRefNode *p;
  726. {
  727.     require(p!=NULL, "pRuleRef: NULL node");
  728.     require(p->ntype==nRuleRef, "pRuleRef: not rule ref node");
  729.     
  730.     printf( " %s", p->text);
  731.     PRINT(p->next);
  732. }
  733.  
  734. /* How to print out a terminal node */
  735. void
  736. pToken(p)
  737. TokNode *p;
  738. {
  739.     require(p!=NULL, "pToken: NULL node");
  740.     require(p->ntype==nToken, "pToken: not token node");
  741.  
  742.     printf( " %s", TerminalString(p->token));
  743.     PRINT(p->next);
  744. }
  745.  
  746. /* How to print out a terminal node */
  747. void
  748. pAction(p)
  749. ActionNode *p;
  750. {
  751.     require(p!=NULL, "pAction: NULL node");
  752.     require(p->ntype==nAction, "pAction: not action node");
  753.     
  754.     PRINT(p->next);
  755. }
  756.  
  757.                     /* F i l l  F o l l o w  L i s t s */
  758.  
  759. /*
  760.  * Search all rules for all rule reference nodes, q to rule, r.
  761.  * Add q->next to follow list dangling off of rule r.
  762.  * i.e.
  763.  *
  764.  *        r: -o-R-o-->o--> Ptr to node following rule r in another rule
  765.  *                    |
  766.  *                    o--> Ptr to node following another reference to r.
  767.  *
  768.  * This is the data structure employed to avoid FOLLOW set computation.  We
  769.  * simply compute the FIRST (reach) of the EndRule Node which follows the
  770.  * list found at the end of all rules which are referenced elsewhere.  Rules
  771.  * not invoked by other rules have no follow list (r->end->p1==NULL).
  772.  * Generally, only start symbols are not invoked by another rule.
  773.  *
  774.  * Note that this mechanism also gives a free cross-reference mechanism.
  775.  *
  776.  * The entire syntax diagram is layed out like this:
  777.  *
  778.  * SynDiag
  779.  *    |
  780.  *    v
  781.  *    o-->R1--o
  782.  *    |
  783.  *    o-->R2--o
  784.  *    |
  785.  *    ...
  786.  *    |
  787.  *    o-->Rn--o
  788.  *
  789.  */
  790. void
  791. FoLink(p)
  792. Node *p;
  793. {
  794.     RuleEntry *q;
  795.     Junction *j = (Junction *) p;
  796.     RuleRefNode *r = (RuleRefNode *) p;
  797.  
  798.     if ( p==NULL ) return;
  799.     require(p->ntype>=1 && p->ntype<=NumNodeTypes,    "FoLink: invalid diagram node");
  800.     switch ( p->ntype )
  801.     {
  802.         case nJunction :
  803.             if ( j->visited ) return;
  804.             if ( j->jtype == EndRule ) return;
  805.             j->visited = TRUE;
  806.             FoLink( j->p1 );
  807.             FoLink( j->p2 );
  808.             j->visited = FALSE;
  809.             return;
  810.         case nRuleRef :
  811.             q = (RuleEntry *) hash_get(Rname, r->text);
  812.             if ( q == NULL )
  813.             {
  814.                 warnNoFL( eMsg1("rule %s not defined",r->text) );
  815.             }
  816.             else
  817.             {
  818.                 if ( r->parms!=NULL && RulePtr[q->rulenum]->pdecl==NULL )
  819.                 {
  820.                     warnFL( eMsg1("rule %s accepts no parameter(s)", r->text),
  821.                             FileStr[r->file], r->line );
  822.                 }
  823.                 if ( r->parms==NULL && RulePtr[q->rulenum]->pdecl!=NULL )
  824.                 {
  825.                     warnFL( eMsg1("rule %s requires parameter(s)", r->text),
  826.                             FileStr[r->file], r->line );
  827.                 }
  828.                 if ( r->assign!=NULL && RulePtr[q->rulenum]->ret==NULL )
  829.                 {
  830.                     warnFL( eMsg1("rule %s yields no return value(s)", r->text),
  831.                             FileStr[r->file], r->line );
  832.                 }
  833.                 if ( r->assign==NULL && RulePtr[q->rulenum]->ret!=NULL )
  834.                 {
  835.                     warnFL( eMsg1("rule %s returns a value(s)", r->text),
  836.                             FileStr[r->file], r->line );
  837.                 }
  838.                 if ( !r->linked )
  839.                 {
  840.                     addFoLink(    r->next, r->rname, RulePtr[q->rulenum] );
  841.                     r->linked = TRUE;
  842.                 }
  843.             }
  844.             FoLink( r->next );
  845.             return;
  846.         case nToken :
  847.             FoLink( ((TokNode *)p)->next );
  848.             return;
  849.         case nAction :
  850.             FoLink( ((ActionNode *)p)->next );
  851.             return;
  852.         default :
  853.             fatal("invalid node type");
  854.     }
  855. }
  856.  
  857. /*
  858.  * Add a reference to the end of a rule.
  859.  *
  860.  * 'r' points to the RuleBlk node in a rule.  r->end points to the last node
  861.  * (EndRule jtype) in a rule.
  862.  *
  863.  * Initial:
  864.  *        r->end -->     o
  865.  *
  866.  * After:
  867.  *        r->end -->     o-->o--> Ptr to node following rule r in another rule
  868.  *                        |
  869.  *                        o--> Ptr to node following another reference to r.
  870.  *
  871.  * Note that the links are added to the head of the list so that r->end->p1
  872.  * always points to the most recently added follow-link.  At the end, it should
  873.  * point to the last reference found in the grammar (starting from the 1st rule).
  874.  */
  875. addFoLink(p,rname,r)
  876. Node *p;
  877. char *rname;
  878. Junction *r;
  879. {
  880.     Junction *j;
  881.     require(r!=NULL,                "addFoLink: incorrect rule graph");
  882.     require(r->end!=NULL,            "addFoLink: incorrect rule graph");
  883.     require(r->end->jtype==EndRule,    "addFoLink: incorrect rule graph");
  884.     require(p!=NULL,                "addFoLink: NULL FOLLOW link");
  885.  
  886.     j = newJunction();
  887.     j->rname = rname;            /* rname on follow links point to target rule */
  888.     j->p1 = p;                    /* link to other rule */
  889.     j->p2 = (Node *) r->end->p1;/* point to head of list */
  890.     r->end->p1 = (Node *) j;    /* reset head to point to new node */
  891. }
  892.  
  893. void
  894. GenCrossRef(p)
  895. Junction *p;
  896. {
  897.     set a;
  898.     Junction *j;
  899.     RuleEntry *q;
  900.     unsigned e;
  901.     require(p!=NULL, "GenCrossRef: why are you passing me a null grammar?");
  902.  
  903.     printf("Cross Reference:\n\n");
  904.     a = empty;
  905.     for (; p!=NULL; p = (Junction *)p->p2)
  906.     {
  907.         printf("Rule %11s referenced by {", p->rname);
  908.         /* make a set of rules for uniqueness */
  909.         for (j = (Junction *)(p->end)->p1; j!=NULL; j = (Junction *)j->p2)
  910.         {
  911.             q = (RuleEntry *) hash_get(Rname, j->rname);
  912.             require(q!=NULL, "GenCrossRef: FoLinks are screwed up");
  913.             set_orel(q->rulenum, &a);
  914.         }
  915.         for (; !set_nil(a); set_rm(e, a))
  916.         {
  917.             e = set_int(a);
  918.             printf(" %s", RulePtr[e]->rname);
  919.         }
  920.         printf(" }\n");
  921.     }
  922.     set_free( a );
  923. }
  924.